package mao.leetcode.array.leetcode31;

public class Solution {

    public void nextPermutation(int[] nums) {
        int i = nums.length-2;
        while (i>=0 && nums[i]>=nums[i+1]){
            i--;
        }
        if (i < 0) {  // 已经成为最大序了。
            reverse(0,nums.length-1,nums);
            return;
        }
        int j=0;
        for ( j = nums.length-1; j > i ; j--) {
            if (nums[j] > nums[i])
                break;
        }
        swap(i,j,nums);
        reverse(i+1,nums.length-1,nums);
        return;
    }

    public void reverse(int start,int end,int[] nums){
       while (start<end){
           int temp = nums[start];
           nums[start] = nums[end];
           nums[end] = temp;
           start++;
           end--;
       }
    }

    public void swap(int from,int to,int[] nums){
        int temp=nums[from];
        nums[from] = nums[to];
        nums[to] = temp;
    }
}
